package org.czl.leetCode1;

import java.util.PriorityQueue;

public class L2290 {
    int[] xx = new int[]{0, 0, 1, -1};
    int[] yy = new int[]{1, -1, 0, 0};
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] distance = new int[m][n];
        boolean[][] set = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        if(grid[0][0] == 1){
            distance[0][0] = 1;
        }else{
            distance[0][0] = 0;
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        queue.add(new int[]{0,0, distance[0][0]});
        while(!queue.isEmpty()){
            int[] r = queue.poll();
            int x = r[0];
            int y = r[1];
            int coin = r[2];
            if(set[x][y]){
                continue;
            }
            if(x == m - 1 && y == n - 1){
                return coin;
            }
            set[x][y] = true;
            for(int i = 0; i < 4; i++){
                int fx = xx[i] + x;
                int fy = yy[i] + y;
                if(fx >= 0 && fx < m && fy >= 0 && fy < n && !set[fx][fy]){
                    if(grid[fx][fy] == 0 && coin < distance[fx][fy]){
                        distance[fx][fy] = coin;
                        queue.add(new int[]{fx, fy, coin});
                    }

                    if(grid[fx][fy] == 1 && coin + 1 < distance[fx][fy]){
                        distance[fx][fy] = coin + 1;
                        queue.add(new int[]{fx, fy, coin + 1});
                    }
                }
            }
        }
        return distance[m - 1][n - 1];
    }
}
